# -*- coding: utf-8 -*-

"""1092. 最短公共超序列
给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。
（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）

示例：
输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

提示：
1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。"""

class Solution:
    """找到最长公共子序列，然后把各自的差异部分补充进去。
    先利用双指针扫描一遍两个字符串，将相同字符对标记出来，可以形成矩阵。
    最后就是在矩阵中寻找最多字符对的路径。
    路径跑出来之后，就可以顺理成章的形成最短公共子序列了。"""
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        """利用状态转移方程填充动态规划结果，既以(i,j)为左上顶角的矩阵最大公共子序列长度"""
        size1, size2, matrix, dp = len(str1), len(str2), [], []

        for _ in range(size1):
            matrix.append([0]*size2)
            dp.append([float('-inf')]*size2)

        # 构建字符一致性位置矩阵
        i = 0
        while i < size1:
            j = 0
            while j < size2:
                if str1[i] == str2[j]:
                    matrix[i][j] = 1
                j += 1
            i += 1

        # print(matrix)

        # 利用动态规划，寻找最长公共子序列长度，并类似缓存的结果保存到动态规划数组中
        def longgest_common_subsequence(i, j):
            if i>= size1 or j >= size2:
                return 0
            
            if dp[i][j] != float('-inf'):
                return dp[i][j]

            if matrix[i][j] == 1:
                rs = longgest_common_subsequence(i+1, j+1) + 1
            else:
                rs = max(longgest_common_subsequence(i, j+1), longgest_common_subsequence(i+1, j))
            
            dp[i][j] = rs
            return rs

        subsequence_size = longgest_common_subsequence(0, 0)

        # print(dp)
        # print(subsequence_size)

        # 利用动态规划表和最大公共子序列长度值，构建一条最大公共子序列
        subsequence = []
        def choose_subsequence(i, j, size):
            if i >= size1 or j >= size2:
                return
            if size == 0:
                return

            if matrix[i][j] == 1 and dp[i][j] == size:
                subsequence.append((i,j))
                choose_subsequence(i+1, j+1, size-1)
            else:
                if j+1 < size2 and dp[i][j+1] == size:
                    choose_subsequence(i, j+1, size)
                elif i+1 < size1 and dp[i+1][j] == size:
                    choose_subsequence(i+1, j, size)

        choose_subsequence(0, 0, subsequence_size)

        # print(subsequence)

        # 拼接最短公共超序列
        p1, p2, supersequence = 0, 0, ''
        for c1, c2 in subsequence:
            supersequence += str1[p1:c1]
            supersequence += str2[p2:c2]
            supersequence += str1[c1]

            p1 = c1 + 1
            p2 = c2 + 1

        if p1 < size1:
            supersequence += str1[p1:]
        
        if p2 < size2:
            supersequence += str2[p2:]

        return supersequence

if __name__ == '__main__':
    print(Solution().shortestCommonSupersequence(str1 = "abac", str2 = "cab"))
    print(Solution().shortestCommonSupersequence(str1 = "bbbaaaba", str2 = "bbababbb"))
    print(Solution().shortestCommonSupersequence(str1 = "bcaaacbbbcbdcaddadcacbdddcdcccdadadcbabaccbccdcdcbcaccacbbdcbabb", str2 = "dddbbdcbccaccbababaacbcbacdddcdabadcacddbacadabdabcdbaaabaccbdaa"))
